package com.zhugang.week03;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * @program algorithms
 * @description: removeDuplicates
 * @author: chanzhugang
 * @create: 2022/06/09 08:07
 */
public class RemoveDuplicates2 {

    public static void main(String[] args) {
        RemoveDuplicates2 removeDuplicates2 = new RemoveDuplicates2();
        String s = "abbba";
        String res = removeDuplicates2.removeDupllicates3(s);
        System.out.println(res);
    }

    /**
     * 1047. 删除字符串中的所有相邻重复项
     * <p>
     * abbaca -> ca
     *
     * @return
     */
    public String removeDuplicates(String s) {
        /**
         * 队列不等于空或者当前字符不等于队尾元素，插入队列；否则删除队尾元素
         */
        Deque<Character> deque = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (deque.isEmpty() || deque.peekLast() != c) {
                deque.addLast(c);
            } else {
                deque.pollLast();
            }
        }
        StringBuilder sb = new StringBuilder();
        while (!deque.isEmpty()) {
            sb.append(deque.pollFirst());
        }

        return sb.toString();
    }

    public String removeDuplicates2(String s) {
        /**
         * 栈实现
         */
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (stack.isEmpty() || stack.peek() != c) {
                stack.push(c);
            } else {
                stack.pop();
            }
        }
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        // 反转字符串
        return sb.reverse().toString();
    }


    public String removeDupllicates3(String s) {
        /**
         * StringBulider 实现:类似栈
         */
        StringBuilder sb = new StringBuilder();
        int top = -1;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (top >= 0 && sb.charAt(top) == c) {
                sb.deleteCharAt(top);
                top--;
            } else {
                sb.append(c);
                top++;
            }
        }
        return sb.toString();
    }

}